스택의 구현

• 배열
• 동적 배열
• 연결 리스트

배열로 구현

정적 크기의 배열을 만들고, 보조 배열을 하나 만들어야 한다.
보조 배열에는 top의 인덱스, 배열의 용량, 배열의 주소값을 가지는 포인터를 넣는다.

장점 : 시간 복잡도는 항상 O(1)이다. 왜냐하면 항상 마지막 top에 있는것에만 접근 가능하니까.
단점 : 배열에서와 마찬가지로 크기를 미리 지정해야된다는 것. 그래서 스택이 다 차면 더 이상 활용하지 못한다.

동적 배열로 구현

일반 배열의 문제를 해결하기 위해서

1. 스택이 가득 찰 때마다 배열의 크기를 1씩 증가시키면?
   배열 크기를 늘릴때마다 새로운 배열을 만들고 거기에 모든 요소들을 복사해서 넣어주고 하는 이 과정들이 너무 오래걸림.
   O(n2)의 시간이 걸린다.

1+2+3+4+5=15 인데?
15 는 5(5+1)/2 와 같다. 1+2+3+4+...+n = n(n+1)/2.
n2가 있기 때문에 빅오 표기법에서는 가장 큰 차수가 있는 항을 작성한다는 규칙에 따라 O(n2).

2. 두 배 확장
   반복이 매 번 발생하지 않기 때문에 1번 방법보다 훨씬 빠르다.
   O(n)의 복잡도.

일단 1부터 n까지 배열의 크기를 2배로 늘리는 횟수는 log2​n번 일어난다.
n=16이라고 한다면 4번. 1+2+4+8 그러니까 log2​n의 값을 k라고 하면 20+21+.....+2k−1 번 만큼 복사가 이루어진다.
그리고 2의 0승부터 k-1승까지의 수를 더한 것은 2n−1과 같다(계산해보면).
스택에 무언가를 넣을때 삽입하는 횟수 + 복사하는 횟수 라고 보면 복사하는 횟수를 찾았으니 삽입하는 횟수를 찾아보자.
간단히 n개를 입력하면 1번씩 n회 입력하니까 n번.
복사 횟수(2n-1) + 삽입 횟수(n) = 3n-1
빅오 표기법에 의해 상수들은 제거하니까 O(n)의 복잡도가 된다.

그런데 amortized 시간복잡도는 O(1)라고 한다.

amortized란?
사전에는 '분할 상환'이라는데, 대략 평균적인 복잡도를 계산해보면 n이 아니라 1이 걸린다는 것. (n/n = 1)